#ifndef QUEUE_H
#define QUEUE_H

/* struct Node {
        DataType_s_q val;
        struct Node *next;
};
typedef struct Node *PNode; */

struct QNode {
        PNode front, rear;
        int len;
        int MaxSize;
};
typedef struct QNode *LinkQueue;


LinkQueue createEmptyQueue_link(void);
Bool isEmptyQueue_link(LinkQueue Q);
DataType_s_q frontQueue_link(LinkQueue Q);
void enQueue_link(LinkQueue Q, DataType_s_q x);
void deQueue_link(LinkQueue Q);
LinkQueue createLinkQueue_H(void);
void print_queue(LinkQueue Q);
void destroy_queue(LinkQueue Q);


LinkQueue createEmptyQueue_link(void)
{
        LinkQueue Q = (LinkQueue)malloc(sizeof(struct QNode));
        if (!Q) {
                printf("Out of memory! Can't malloc a queue!\n");
        }
        Q->MaxSize = MAX_NUM;
        Q->len = 0;
        Q->front = NULL;
        Q->rear = NULL;
        return Q;
}

Bool isEmptyQueue_link(LinkQueue Q)
{
        return Q->front == NULL;
}

DataType_s_q frontQueue_link(LinkQueue Q)
{
        if (isEmptyQueue_link(Q)) return FLAG;
        return Q->front->val;
}

void enQueue_link(LinkQueue Q, DataType_s_q x)
{
        // 判断队列是否满.
        if (Q->MaxSize <= Q->len) {
                printf("The queue is full now, Can't enqueue!\n");
                return ;
        }
        PNode p = (PNode)malloc(sizeof(struct Node));
        if (!p) {
                printf("Out of memory! Can't malloc a PNode to enqueue!\n");
        }
        p->val = x;
        if (Q->rear == NULL && Q->front == NULL) {
                p->next = NULL;
                Q->front = p;
        } else {
                p->next = Q->rear->next;
                Q->rear->next = p;
        }
        // 入队后，记得更新len和rear.
        Q->rear = p;
        Q->len++;
}

void deQueue_link(LinkQueue Q)
{
        // 判断队列是否为空.
        if (Q->len <= 0) {
                printf("The queue is empty now!Can't dequeue!\n");
                return ;
        }
        PNode tmp = Q->front;
        if (Q->rear == Q->front) {
                Q->front = Q->rear = NULL;
        } else {
                Q->front = Q->front->next;
        }
        free(tmp);
}

void destroy_queue(LinkQueue Q)
{
        if (isEmptyQueue_link(Q)) return ;
        PNode p, q;
        PNode tmp;
        p = Q->front;
        q = Q->front;
        while (q != NULL && q->next != NULL) {
                tmp = p;
                p = p->next;
                q = q->next->next;
                free(tmp);
        }
        free(Q);
}

void print_queue(LinkQueue Q)
{
        if (isEmptyQueue_link(Q)) {
                printf("Now the queue is empty!\n");
                return ;
        }
        PNode p;
        for (p = Q->front; p != NULL; p = p->next)
        {
                printf("%p ", p->val);
        }
        printf("\n");
}
#endif
